package LeetCodeQuestionBank;

/**
 * 278. 第一个错误的版本
 * 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 *
 * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 *
 * 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 *
 *
 * 示例 1：
 *
 * 输入：n = 5, bad = 4
 * 输出：4
 * 解释：
 * 调用 isBadVersion(3) -> false
 * 调用 isBadVersion(5) -> true
 * 调用 isBadVersion(4) -> true
 * 所以，4 是第一个错误的版本。
 * 示例 2：
 *
 * 输入：n = 1, bad = 1
 * 输出：1
 *
 * 提示：
 *
 * 1 <= bad <= n <= 231 - 1
 */
public class T278 {

    public int firstBadVersion(int n) {

        //同样是二分查找
        //1 定义左指针 从1开始
        int left = 1;
        boolean leftResult = isBadVersion(1);
        //2 定义右指针
        int right = n;
        boolean rightResult = isBadVersion(n);

        if (n==1){
            return 1;
        }

        while (left<right){

            int temp = left+(right-left)/2; //中间值
            //左右
            if (leftResult==rightResult){
                break;
            }
            //如果中间版本是正确的 移动左指针
            if (false==isBadVersion(temp)){
                left = temp+1;
                leftResult = isBadVersion(left);
            }
            //如果中间版本是错误的 移动右指针
            if (true==isBadVersion(temp)){
                right = temp-1;
                rightResult = isBadVersion(right);
            }

        }

        if (leftResult==false&&rightResult==false){
            return right+1;
        }else {
            return left;
        }


    }

//1420736637
//1150769282
    //模拟
    public boolean isBadVersion(int n){

        if (n<1150769282){
            return false;
        }else {
            return true;
        }

    }

    public static void main(String[] args) {

        T278 t278 = new T278();
        int i = t278.firstBadVersion(1420736637);
        System.out.println(i);

    }


}
